//https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        queue<TreeNode*> t;
        if (root == nullptr)
            return ret;

        t.push(root);
        int level = 1;
        while (t.size())
        {
            int sz = t.size();
            vector<int> temp;
            for (int i = 0; i < sz; i++)
            {
                TreeNode* top = t.front();
                t.pop();
                temp.push_back(top->val);

                if (top->left) t.push(top->left);
                if (top->right) t.push(top->right);
            }
            if (level % 2 == 0) reverse(temp.begin(), temp.end());
            level++;
            ret.push_back(temp);
        }

        return ret;

    }
};